\documentclass[a4paper,12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[french]{babel}

\title{Rapport de Projet de compilation\\Clausspilator, the C-- compiler}
\author{Guillaume Dott\\David Babel\\M1 ILC}
\date{\today}
\begin{document}
\maketitle
\section{Introduction}
 
Dans ce projet, il nous est demandé de créer un compilateur capable de transformer une source d'un sous ensemble du langage C, en langage assembleur MIPS R2000. Ce langage doit comporter des opérations, des instructions basiques de lecture et d'écriture, la gestion des expressions booléennes, ainsi que des structures conditionnelles de base.
 
\section{Choix de conception}
 
\subsection{Table des symboles}
Nous avons choisi d'utiliser une liste chaînée comme table des symboles. A l'aide d'une structure \textbf{"cellule"} qui contient une référence vers la cellule suivante, nous pouvons parcourir, ajouter et supprimer facilement des cellules sans avoir à utiliser des tableaux dynamiques.
Nous avons donc codé plusieurs fonctions pour utiliser facilement cette liste chaînée comme une fonction pour ajouter une cellule, ou pour libérer complètement la mémoire occupée par la liste.
 
De plus nous avons choisi d'utiliser une table par type de variable. Nous avons donc 4 tables, pour les \textbf{int}, les \textbf{float}, les pointeurs et les chaînes de caractères. Cela permet de ne pas avoir à parcourir toutes les variables déclarées pour chercher un type particulier.
Nous avons choisi de traiter les variables temporaires de la même façon que les autres variables. La création de variables temporaires ajoute une variable sans nom à la table des symboles, et il est ainsi très pratique d'y acceder.
Lors de la génération du code, chaque table des symboles ajoute une ligne dans la partie .data pour avoir un tableau de \textbf{int}, un tableau de \textbf{float}, un tableau de pointeurs et de chaîne de caractère et ainsi accéder aux différentes variables avec leur adresse de manière optimisée ( pas une ligne par variable ).
 
\subsection{Stockage des quadruplets}
 
Le parcours du code crée une liste chaînée de quadruplets qui sont utilisés pour générer le code MIPS à la fin du parcours du fichier source.
Pour ne pas surcharger la structure des quadruplets, nous avons choisi de gérer les labels dans une liste à part. En effet, une liste contient les ID des quadruplets qui nécessitent un label qui sera alors ajouté lors de la génération du code final uniquement si celui ci est pointé par une instruction de type \textbf{"GOTO"}.
 
\subsection{Les expressions booléennes}
 
Pour gérer les conditions et les expressions booléennes, nous utilisons des marqueurs de position pour pouvoir retourner le résultat booléen sans évaluer la totalité de l'expression comme proposé dans la version avancée du cours.
 
\subsection{La gestion des expressions}
 
La structure \textbf{"s\_expression"} permet de remonter l'adresse ( ptr ) ainsi que le type de l'expression courante de la grammaire (opération, identifiant, \ldots) à l'expression supérieure. 
Il est nécessaire d'avoir ces informations pour pouvoir vérifier la cohérence des types et pouvoir effectuer les calculs avec le résultat de cette expression, conformément à ce qui était indiqué dans le cours.
 
\section{Problèmes rencontrés}
 
Le principal problème que nous avons rencontré a été de transposer les algorithmes vus en cours en code concret. Il nous a fallu imaginer les objets à utiliser et implémenter les structures de chaînage des éléments pour que cela reste cohérent avec les concepts et algorithmes  du cours. 
De même, il nous a fallu construire nos fonctions en rapport avec nos choix de conceptions. Il n'a pas toujours été facile d'implémenter les algorithmes que nous ne comprenions pas bien au début.
 
Dans la première version de notre compilateur, nous génériions le code au fur à mesure du parsing du code source, mais lorsqu'il a fallu travailler sur les conditions et les expressions booléennes nous nous sommes rendu compte qu'il était indispensable de stocker la liste des quadruplets à générés à cause de ceux qui étaient générés de manière incomplète durant ce parsing.
 
Un autre problème rencontré sur lequel nous avons perdu un peu de temps fut le chaînage de ces quadruplets. Initialement, nous n'avions qu'une liste de quad qui était remplie tout au long du programme puis parcouru en fin de programme pour écrire le code mips final si tout s'était bien passé. 
Hors cette structure de quadruplet contenait alors, elle même un pointeur vers le quad suivant, le chaînage était donc interne aux éléments. Seulement, lorsqu'il nous a fallu développer les parties booléennes et les conditions nous avons utilisé d'autres listes ( true, false et next ) qui contenaient également des pointeurs sur des quad. Cela a créer des conflits au niveau du chaînage des éléments et il a donc fallu sortir ce chaînage des quadruplets.
Nous avons donc introduit une structure de liste indépendante pour chaîner les quadruplets entre eux, indispensable pour avoir accès à des sous-listes de quad sans modifier le chaînage de la liste principale des quads à générer, tout en gardant un pointeur vers ces éléments.
 
De manière générale, il n'a pas été très difficile de comprendre ou de générer des instructions de code mips, mais parfois il n'était pas simple pour le compilateur de les générer de manière "dynamique" et ce, malgré les algorithmes vus cours.
Suivant les choix de conception, il était important de bien comprendre les concepts du cour, sous peine d'être complètement perdu si une modification était nécessaire.
 
\section{Fonctionnalités supplémentaires}
 
Nous avons choisi d'enrichir notre grammaire afin d'ajouter diverses fonctionnalités à notre langage, dont voici quelques exemples.
 
\subsection{Makefile}
 
Nous avons réalisé des tests pour chacune des fonctionnalités de notre programme mentionnée ci dessus, pour exécuter les fichiers de test il suffit de les compiler à l'aide de notre compilateur via la commande \textbf{"make tests"} et d'aller dans le dossier \textbf{"./test"} pour lancer les fichiers avec le script shell \textbf{"./run fichier.s"}.
De plus nous avons intégré un "shebang" dans nos fichiers ".s" pour qu'ils puissent être directement exécutés par un petit bash de notre conception. Cela donne l'illusion d'un vrai binaire.
La commande \textbf{"make debug"} permet de compiler notre compilateur en activant les messages de debug. Cela affiche des informations utiles sur le déroulement du compilateur pour la génération des quadruplets lors de la compilation d'un fichier.
 
\subsection{Basics}
 
Nous avons intégré les commentaires type C à notre programme, ainsi que les opérations "\%" et "!", pour facilité la réalisation des fichiers d'exemples
 
\subsection{Structures conditionnelles}
 
Grâce à l'utilisation de la version avancée de l'algorithme sur les instructions conditionnelles et des boucles, il est possible d'imbriquer dans notre programme une infinité d'instructions de type \textbf{"if else"},  \textbf{"while"} ou \textbf{"for"} et il est possible d'utiliser les structures conditionnelles de type \textbf{"else if"};
Nous avons également introduit une version simplifiée de l'opérateur ternaire que l'on retrouve en C sous la forme : \textbf{" ( condition ) ? instruction : instruction ;"}
 
\subsection{Structures itératives}
 
Pour implémenter le for "classique" du C, il a été nécessaire de complexifier un peu la grammaire en sous règles pour pouvoir produire une règle de la forme \textbf{"for( liste\_affections ; test ; affectation )"}
N'ayant pas l'algorithme dans le cours, il a été nécessaire de s'intéresser en profondeur au fonctionnement des marqueurs, et de comprendre précisément leur fonctionnement.
Nous avons aussi implémenté les indispensables instructions incrémentales \textbf{"++"} et textbf{"--"} à utiliser avec les boucles.
 
\subsection{Les pointeurs}
 
Notre compilateur gère les pointeurs de pointeur avec un nombre non limité d'indirections. De plus, toutes les opérations peuvent être effectuées sur les valeurs vers lesquelles pointent ces pointeurs.
 
\subsection{Instruction Write}
 
Nous avons rajouté la possibilité d'afficher des constantes sans passer par une variable ainsi que la possibilité d'afficher une chaine à l'aide des instructions \textbf{"printf constante;"} et \textbf{"printf chaine;"}.
 
\section{Conclusion}
 
Nous avons donc atteint l'objectif visé par ce projet, à savoir de réaliser un compilateur capable de transformer un code source simple, en langage assembleur MIPS.
Nous avons implémenter les fonctionnalités demandés en utilisant les méthodes les plus avancées ( utilisation des marqueurs ) et il a été plaisant par la suite d'implémenter de nouvelles fonctionnalités et d'enrichir la grammaire et ainsi améliorer notre langage et notre compilateur. 
C'est l'un des projets les plus intéressant que nous ayons été amenés à réaliser et nous nous réjouissons fortement du résultat obtenu.
 
\end{document}
